package _11_整理题目._2_二叉树_递归_dfs_bfs._dfs_路径和;


import org.junit.Test;
import util.TreeNode;

/**
 * https://leetcode-cn.com/problems/path-sum/
 *
 * 给定一个二叉树和一个值 target，判断是否有从根节点到叶子节点的节点值之和等于 target 的路径
 *
 * dfs 遍历，直至到达叶子节点 求和
 *
 */
public class _061_二叉树中是否存在节点和为指定值的路径 {
    
    private boolean flag = false;
    
    public boolean hasPathSum (TreeNode root, int target) {
        dfs(root, 0, target);
        return flag;
    }
    
    private void dfs(TreeNode root, int sum, int target) {
        if(root == null || flag == true) return;
        
        sum += root.val;
        if(root.left==null && root.right==null && sum==target) {
            flag = true;
        }

        dfs(root.left, sum, target);
        dfs(root.right, sum, target);
    }
    
    @Test
    public void main() {
        Integer[] input = {5, 4, 8, 1, 11, null, 9, null, null, 2, 7};
        TreeNode root = TreeNode.getTreeFromArray(input);
        System.out.println(hasPathSum(root, 22));// true
    }
    
}
